package com.tree;

/**
 * 第三次优化:
 * 并查集基于 rank 的优化:
 * 我们之前根据整个树中元素的数量来使元素少的连接到元素多的根上,但是其实这样也是有风险的
 * 比如平躺着的10个元素为一棵树,垂直放着的5个元素为一棵树,根据3代中的逻辑,垂直的树元素少,因此要连接在平躺着的树上,
 * 这样无形之中增加了树的高度,因此这次优化,我们通过记录数的高度(rank),来判断谁要连接在谁上
 */
public class UnionFindImpl_4 extends UnionFindImpl_2 implements IUnionFind {

    private int[] rank;//rank[k] 表示以 k 为根的集合所表示的数的层数

    /*假如一个树层数为3,另一个层数为5,这时连接两棵树时
     *只需要把 3 的连接到 5 上,并不需要修改他们的层数.
     *而只有两个树的层数相等时,被连接的那个数会使原来的层数 +1 */
    @Override
    public void union(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (rank[pRoot] < rank[qRoot]) {
            super.union(pRoot, qRoot);
        } else if (rank[pRoot] > rank[qRoot]) {
            super.union(qRoot, pRoot);
        } else {
            super.union(pRoot, qRoot);
            rank[qRoot] += 1;
        }
    }

    public UnionFindImpl_4(int count) {
        super(count);
        rank = new int[count];
        for (int i = 0; i < count; i++) {
            rank[i] = 1;
        }
    }


}
